package OptimalAlgorithm.DivideAndConquer_Merge;
//https://leetcode.cn/problems/reverse-pairs/description/
public class ReversePairs_Two {
    public int reversePairs(int[] nums) {
        int ret = 0;
        return mergeSort(nums,0,nums.length - 1,ret);
    }
    private int mergeSort(int[] nums,int left,int right,int ret){
        if(left >= right){
            return 0;
        }
        int mid = (right + left) / 2;
/* (这是一个错误的写法，无法改变ret的值，改变的只是ret的副本)
        ret += mergeSort(nums,left,mid,ret);//左半部分的翻转对
        ret += mergeSort(nums,mid + 1,right,ret);//右半部分翻转对
        //1、求一左一右的翻转对(在是有序数组的前提下：升序)
        ret += count(nums,left,mid,right);*/
        int count = mergeSort(nums,left,mid,ret) + mergeSort(nums,mid + 1,right,ret) + count(nums,left,mid,right);
        //2、归并排序(让数组有序)
        merge(nums,left,mid,right);
        return count;
    }
    //本题也可以用降序来做，思路一样的
    private int count(int[] nums,int left,int mid,int right){
        int count = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        while (s2 <= e2){
            while (s1 <= e1 && nums[s1] / 2.0 <= nums[s2]){
                s1++;
            }
            if(s1 > e1){//优化
                break;
            }
            count += e1 - s1 + 1;
            s2++;
        }
        return count;
    }
    private void merge(int[] nums,int left,int mid,int right){//升序
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int index= 0;
        int[] temp = new int[right - left + 1];
        while (s1 <= e1 && s2 <= e2){
            if(nums[s1] >= nums[s2]){
                temp[index++] = nums[s2++];
            }else {
                temp[index++] = nums[s1++];
            }
        }
        while (s1 <= e1){
            temp[index++] = nums[s1++];
        }
        while (s2 <= e2){
            temp[index++] = nums[s2++];
        }
        for (int i = left; i <= right; i++) {
            nums[i] = temp[i - left];
        }
    }
}
